#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0023.py
@time: 2021/9/17 12:43
@desc: https://leetcode-cn.com/problems/valid-sudoku/
'''
class Solution:
    def isValidSudoku(self, board: list) -> bool:
        dic = {}
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                idxs = dic.get(board[i][j], [])
                idxs.append((i,j))
                dic[board[i][j]] = idxs

        for num in range(1,10):
            idxs = dic.get(str(num), None)
            if idxs == None:
                continue
            # 检查有无同行、同列、同格
            row_idx = []
            col_idx = []
            block_idx = []
            for i,j in idxs:
                if len(row_idx)==0 and len(col_idx)==0 and len(block_idx)==0:
                    row_idx.append(i)
                    col_idx.append(j)
                    block_idx.append((i//3, j//3))
                    continue
                # 检查是否同行
                if i in row_idx:
                    return False
                # 检查是否同列
                if j in col_idx:
                    return False
                if (i//3, j//3) in block_idx:
                    return False
                row_idx.append(i)
                col_idx.append(j)
                block_idx.append((i // 3, j // 3))

        return True

if __name__ == '__main__':
    sl = Solution()
    # board = [["5","3",".",".","7",".",".",".","."]
    #         ,["6",".",".","1","9","5",".",".","."]
    #         ,[".","9","8",".",".",".",".","6","."]
    #         ,["8",".",".",".","6",".",".",".","3"]
    #         ,["4",".",".","8",".","3",".",".","1"]
    #         ,["7",".",".",".","2",".",".",".","6"]
    #         ,[".","6",".",".",".",".","2","8","."]
    #         ,[".",".",".","4","1","9",".",".","5"]
    #         ,[".",".",".",".","8",".",".","7","9"]]
    # board = [[".",".","4",".",".",".","6","3","."],
    #          [".",".",".",".",".",".",".",".","."],
    #          ["5",".",".",".",".",".",".","9","."],
    #          [".",".",".","5","6",".",".",".","."],
    #          ["4",".","3",".",".",".",".",".","1"],
    #          [".",".",".","7",".",".",".",".","."],
    #          [".",".",".","5",".",".",".",".","."],
    #          [".",".",".",".",".",".",".",".","."],
    #          [".",".",".",".",".",".",".",".","."]]
    board = [[".",".",".",".",".",".",".",".","."],
             [".",".",".",".",".",".",".",".","."],
             [".","9",".",".",".",".",".",".","1"],
             ["8",".",".",".",".",".",".",".","."],
             [".","9","9","3","5","7",".",".","."],
             [".",".",".",".",".",".",".","4","."],
             [".",".",".","8",".",".",".",".","."],
             [".","1",".",".",".",".","4",".","9"],
             [".",".",".","5",".","4",".",".","."]]
    res = sl.isValidSudoku(board)
    print(res)
